Τι (ποιος) είναι ЕВКЛИДА АЛГОРИТМ - ορισμός

АЛГОРИТМ ДЛЯ НАХОЖДЕНИЯ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ ДВУХ ЦЕЛЫХ ЧИСЕЛ

Алгоритм Эвклида; Евклида алгоритм; Xgcd; Теорема Ламе

Евклида алгоритм

способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме в "Началах" Евклида. Для случая положительных чисел а и b, причём a ≥ b, этот способ состоит в следующем. Деление с остатком числа а на число b всегда приводит к результату а = nb + b₁, где частное n - целое положительное число, а остаток b₁ - либо 0, либо положительное число, меньшее b (0 ≤ b₁ < b). Будем производить последовательное деление:

где все n_i - положительные целые числа и 0 ≤ b₁ < b_i-1 до тех пор, пока не получится остаток, равный нулю. Этот последний остаток b_k+1 можно не писать, так что ряд равенств (*) закончится так:

b_k-2 = n_k-1 + b_k,

b_k-1 = n_kb_k.

Последний положительный остаток b_к в этом процессе и является наибольшим общим делителем чисел а и b. Е. а. служит не только для нахождения наибольшего общего делителя, но и для доказательства его существования. В случае многочленов или отрезков поступают сходным образом. В случае несоизмеримых отрезков (см. Соизмеримые и несоизмеримые величины) Е. а. оказывается бесконечным.

ЕВКЛИДА АЛГОРИТМ

способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом.

Алгоритм Евклида

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век ), который впервые описал его в VII и X книгах «Начал».

https://ru.wikipedia.org/wiki/Алгоритм_Евклида

Βικιπαίδεια

Алгоритм Евклида

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII и X книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время.

В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX веке он был обобщён на другие типы математических объектов, включая целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида был обобщён на другие математические структуры, такие как узлы и многомерные полиномы.

Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений, при построении непрерывных дробей, в методе Штурма. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких как теорема Лагранжа о сумме четырёх квадратов и основная теорема арифметики.

https://ru.wikipedia.org/wiki/Алгоритм Евклида